package com.lw.leetcode.bingChaJi.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 928. 尽量减少恶意软件的传播 II
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/12 17:46
 */
public class MinMalwareSpread928 {

    private int[] arr;

    public int minMalwareSpread(int[][] graph, int[] initial) {
        Arrays.sort(initial);
        int length = graph.length;
        arr = new int[length];
        int[] counts = new int[length];
        int[] flags = new int[length];
        int min = Integer.MAX_VALUE;
        int index = -1;
        int size = initial.length;
        for (int k = 0; k < size; k++) {
            int del = initial[k];
            Arrays.fill(counts, 0);
            Arrays.fill(flags, 0);
            for (int i = 0; i < length; i++) {
                arr[i] = i;
            }
            for (int i = 0; i < length; i++) {
                if (i == del) {
                    continue;
                }
                for (int j = i + 1; j < length; j++) {
                    if (j == del) {
                        continue;
                    }
                    if (graph[i][j] == 1) {
                        int a = find(i);
                        int b = find(j);
                        if (a != b) {
                            arr[Math.max(a, b)] = Math.min(a, b);
                        }
                    }
                }
            }
            for (int i = 0; i < length; i++) {
                counts[find(i)]++;
            }
            int item = 0;
            for (int i1 : initial) {
                int t = find(i1);
                if (flags[t] == 0) {
                    flags[t] = 1;
                    item += counts[t];
                }
            }
            if (item < min) {
                min = item;
                index = del;
            }
        }
        return index;
    }

    private int find(int v) {
        if (arr[v] == v) {
            return v;
        }
        int t = find(arr[v]);
        arr[v] = t;
        return t;
    }

}
